Path Sum Series

发表于

Path Sum

Question

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Analysis

  • 不断地在sum上减去当前节点的值看是否为0，递归向下进行。假如某节点为叶节点且sum-root.val==0，返回true
  • 也可构建helper函数进行DFS遍历，利用global变量不断加上节点值，判断是否相等

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null)  return false;
        if(root.left==null&&root.right==null&&sum-root.val==0)  return true;
        return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
    }
}

Path Sum II

Question

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return 

1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]

Analysis

  • DFS遍历过程中碰到加和sum=target将对应序列加入结果res
  • 结束一次遍历时需注意 item.remove(item.size()-1); 移走最后一个元素

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int sum;
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res=new ArrayList<>();
        if(root==null)
            return res;
        List<Integer> item=new ArrayList<>();
        this.sum=sum;
        
        item.add(root.val);
        DFS(root,root.val,item,res);
        return res;
    }
    
    private void DFS(TreeNode node, int num, List<Integer> item, List<List<Integer>> res){
        if(node.left==null&&node.right==null){
            if(num==sum)
                res.add(new ArrayList(item));
            return;
        }
        if(node.left!=null){
            item.add(node.left.val);
            DFS(node.left,num+node.left.val,item,res);
            item.remove(item.size()-1);
        }
        if(node.right!=null){
            item.add(node.right.val);
            DFS(node.right,num+node.right.val,item,res);
            item.remove(item.size()-1);
        }
    }
}

Path Sum III

Question

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Analysis

  • 当遍历到某节点时，找到所以以该节点为终点且取值和可为sum的路径
  • 利用presum保存到该节点的所有可能取值和
  • 查找res-target是否存在于presum是为了判断是否有可从中间开始计数且满足条件的路径
  • 一次遍历结束后需 presum.put(res,presum.get(res)-1); 保证当前存储的都会在后续遍历中构成路径，不影响后续的递归

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int cnt;
    public int pathSum(TreeNode root, int sum) {
        if(root==null)  return 0;
        HashMap<Integer,Integer> presum=new HashMap<>();
        presum.put(0,1);
        return helper(root,0,sum,presum);
    }
    
    public int helper(TreeNode node, int sum, int target, HashMap<Integer,Integer> presum){
        if(node==null)
            return 0;
        int res=sum+node.val;
        int cnt=presum.getOrDefault(res-target,0);
        
        presum.put(res,presum.getOrDefault(res,0)+1);
        cnt+=helper(node.left,res,target,presum)+helper(node.right,res,target,presum);
        presum.put(res,presum.get(res)-1);
        return cnt;
    }
}